// Source : https://leetcode-cn.com/problems/first-bad-version/
// Author : jkbs487
// Date   : 2021-06-14

/***************************************************************************************************** 
 *
 * You are a product manager and currently leading a team to develop a new product. Unfortunately, the 
 * latest version of your product fails the quality check. Since each version is developed based on 
 * the previous version, all the versions after a bad version are also bad.
 * 
 * Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes 
 * all the following ones to be bad.
 * 
 * You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a 
 * function to find the first bad version. You should minimize the number of calls to the API.
 * 
 * Example 1:
 * 
 * Input: n = 5, bad = 4
 * Output: 4
 * Explanation:
 * call isBadVersion(3) -> false
 * call isBadVersion(5) -> true
 * call isBadVersion(4) -> true
 * Then 4 is the first bad version.
 * 
 * Example 2:
 * 
 * Input: n = 1, bad = 1
 * Output: 1
 * 
 * Constraints:
 * 
 * 	1 <= bad <= n <= 231 - 1
 ******************************************************************************************************/

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    // binary search
    int firstBadVersion(int n) {
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid) == false) {
                if (mid+1 < n && isBadVersion(mid+1) == true)
                    return mid+1;
                else 
                    left = mid+1;
            }
            else if(isBadVersion(mid) == true) {
                if (mid-1 >= 0 && isBadVersion(mid-1) == false)
                    return mid;
                else 
                    right = mid-1;
            }
        }
        return n;
    }
};
